package algotithm.acwing.dp.test3;

/**
 * @author zhouyanxiang
 * @Date 2021-03-2021/3/12-23:48
 * AcWing 3. 完全背包问题
4 5
1 2
2 4
3 4
4 5

10


 */
import java.io.*;
public class Main {

    private static int Max = 1010;
    private static int[]v = new int[Max];
    private static int[]w = new int[Max];
    private static int[]f = new int[Max];

    public static void main(String[] args) throws IOException  {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] arr1 = reader.readLine().split(" ");
        int N = Integer.parseInt(arr1[0]);
        int V = Integer.parseInt(arr1[1]);
        int t = N;
        int idx1 = 0, idx2 = 0;
        while (t-- > 0) {
            String[] arr = reader.readLine().split(" ");
            v[idx1++] = Integer.parseInt(arr[0]);
            w[idx2++] = Integer.parseInt(arr[1]);
        }

        for (int i = 0; i < N; i++) {
            for (int j = v[i]; j <= V; j++) {
                f[j] = Math.max(f[j],f[j-v[i]] + w[i]);
            }
        }
        writer.write(f[V] + "\n");
        writer.flush();
        writer.close();
        reader.close();
    }


}